1. Field of Industrial Application
The present invention relates to a Viterbi decoding method and a Viterbi decoder which are executed to determine the most approximate path on two-state state metrics.
2. Description of the Related Art
The Viterbi decoding has been known for the maximum likelihood decoding system for partial responses or convolution codes. The Viterbi decoding system provides a high error-correcting capability for a random error caused on a transmission path, so that the Viterbi decoding system is combined with a partial response when it is used in a data recording and reproducing system. For the data communication system, the Viterbi decoding system is now being applied as a method for decoding convolution codes to satellite communications.
Herein, the description will be oriented to a commonly available data recording and reproducing apparatus which is arranged to allow controllable intra-code interference and combine the Viterbi decoding system with the partial response with higher transmission efficiency.
As shown in FIG. 1, a numeral 101 denotes a modulator, which serves to modulate the data into a proper format to a recording medium 104, for example, through the effect of the eight-to-ten modulation. Concretely, the modulator 101 serves to convert the data entered as information series (simply termed the information series) at a terminal 171 into modulated series xt (t=0. 1. 2 . . . ).
A numeral 102 denotes a pre-coder for the partial responses. The pre-coder 102 serves to code the modulated series xt according to the predetermined coding rules for generating medium series yt. The medium series yt are transmitted to a recording head through a recording amplifier 103 and then is recorded on the recording medium 104 through the recording head. As a result of the abovementioned process, the data (information series) entered at the terminal 171 has been recorded on the recording medium 104.
A signal reproduced from the recording medium 104 through a reproduction head is amplified by a reproduction amplifier 105 and then is transmitted to an equalizer 106. The equalizer 106 operates to equalize the waveform of the reproduced signal and then feed an output z onto a transmission path.
A numeral 107 denotes a phase-locked loop (termed PLL) circuit, which operates to extract clock components from the output z on the transmission path having the recording medium 104 on the way. That is, the PLL circuit 107 operates to generate a clock synchronized with the reproduced signal.
A numeral 108 denotes a sampling circuit, which operates to sample the output z for the transmission path on the clock sent from the PLL circuit 107 for converting the output z into data and then supply the resulting sampling series zt to a Viterbi decoder. 109. The Viterbi decoder 109 operates to perform the Viterbi decoding with respect to the sampling series zt and reproduce the modulated series xt for the output of the modulator 101 of the recording system.
A numeral 110 denotes a decoder, which is located to correspond to the modulator 101 of the recording system and operates to demodulate the modulated series xt for reproducing the original information series and then feed the reproduced information series as the decoded series through a terminal 172. These series of operations result in reproducing the data from the recording medium 104.
In turn, the description will be oriented to a transmission system in which the used partial response is (1, 1) (simply termed PR(1, 1)).
The transmission system having PR(1, 1) applied thereto may be represented by the equalizer circuit shown in FIG. 2.
Concretely, this transmission system provides a precoder for PR(1, 1) as its transmitting system. This pre-coder is composed of an exclusive-Or circuit (termed the EXOR circuit) 121 and a delaying unit 122 for delaying the medium series yt that are an output of the EXOR circuit 121 and supplying the delayed signal to the EXOR circuit 121.
The EXOR circuit 121 takes an EXOR of the modulated series xt supplied from the modulator 101 shown in FIG. 1 through the terminal 173 and the medium series yt delayed by a sampling time point by a delaying unit 122. That is, the precoder composed of the EXOR circuit 121 and the delaying unit 122 is served as a Modulo-2 adder (termed the Mod-2 adder). The pre-coder performs a Mod-2 addition with respect to the modulated series xt for generating the medium series yt and then feed the medium series yt onto the transmission path.
The transmission path for PR(1, 1) is equivalent to the circuit composed of the delaying unit 123 for delaying the medium series yt and the adder 124 for adding the medium series yt to the medium series yt-delayed by the delaying unit 123. The delaying unit 123 operates to delay the medium series yt from the EXOR circuit 121 by one sampling time. The adder 124 operates to add the medium series yt to the delayed medium series yt and then feed the output z onto the transmission path.
In the receiving system, the Mod-2 adder 125 performs a modulo-2 addition with respect to the output z for reproducing the modulated series xt. The operation of the Mod-2 addition results in reproducing the modulated series xt and feeding xt through the terminal 174.
The operation of the circuit (termed the PR(1, 1) circuit) covering the range of the EXOR circuit 121 to the adder 124 may be represented by a state transition diagram of FIG. 3.
Concretely, FIG. 3 shows the state transition of PR(1, 1). In the state transition of FIG. 3:
1.sub.00 means that if a value of "0" is entered as an information source in the state S0, a value of "-1" is output and the state is shifted to the state S0; PA1 1.sub.01 means that if a value of "1" is entered as an information source in the state S0, a value of "0" is output and the state is shifted to the state S1; PA1 1.sub.10 means that if a value of "0" is entered as an information source in the state S1, a value of "+1" is output and the state is shifted to the state S1; and PA1 B.fwdarw..DELTA.L.sub.k.sup.S1 is a state metric of the state S1 at the time point t=k
1.sub.11 means that if a value of "1" is entered as an information source in the state S1, a value of "0" is output and then the state is shifted to the state S0.
Next, FIG. 4 is a Trellis diagram in which the state transition is expanded on the time point bases. In this diagram, an arrow from a state to another one is termed a branch, a bunch of branches is termed a path, and a likelihood of each branch is termed a metric.
As is understood from the state transition diagram, in PR(1, 1), when an input signal to the decoder is zero, the reproduced data takes a value of 1. When an input signal is .+-.1, the reproduced data takes a value of 0. The actual signal involves noises. Assuming that the distribution is a Gaussian distribution having a dispersion of .sigma. and an average value of 0, the reproduction distribution of PR(1, 1) is made to be as shown in FIG. 5, so that the probabilities of the following expressions (1) to (4) may be derived.
Expression 1! ##EQU1## PA0 Expression 2! ##EQU2## PA0 Expression 3! ##EQU3## A.fwdarw..DELTA.L.sub.k.sup.S0 is a state metric of the state S0 at the time point t=k PA0 Expression 4! ##EQU4## PA0 Expression PA0 Expression 6! ##EQU5## PA0 Expression
The expression (1) indicates a probability P.sub.11 of sensing .DELTA.y when a value of "1" is reproduced in the state S1. The expression (2) indicates a probability P.sub.10 of sensing .DELTA.y when a value of "0" is reproduced in the state S1. The expression (3) indicates a probability P.sub.01 of sensing .DELTA.y when a value of "1" is reproduced in the state S0. The expression (4) indicates a probability P.sub.00 of sensing .DELTA.y when a value of "0" is reproduced in the state S0.
Herein, a negative logarithm to the probability is defined as a metric.
The metric in the Viterbi decoding system is derived by the comparison of not the absolute values but the relative values. Hence, for normalizing the metric, a constant is added and multiplied to the metric. Assuming that the normalized metric is 1.sub.11, 1.sub.10, 1.sub.01, 1.sub.00, it may be represented as the following expressions (5) to (7).
The Viterbi algorithm is a system of decoding data as restricting the paths to one so that the metric to each state at a time point k (termed the state metric) is made minimum. Hence, the Viterbi algorithm for PR(1, 1) is executed to determine the most approximate path on the following expressions (8) and (9) from the state metrics of the states S0 and S1 at the time point t=k derived from the Trellis diagram of FIG. 4 and the normalized metric and then to decode the data based on the determined most approximate path.
The actual circuit is arranged to determine the most approximate path on this metric calculation and decode the data on the most approximate path.
The arrangement for performing the operations of the expressions (8) and (9) includes an adder and a multiplier, so that it is large in circuit scale and does not have so high an operating speed as expected.
Since the PR(1, 1) has two states, the difference .DELTA.Lk between the metrics (termed the difference metric) as indicated in the following expression (10) is utilized for simplifying the process of the expressions (8) and (9).
Considering the expression (10), a comparison between a common term .DELTA.Lk-1-2yk and .+-.1 (indicating a content in two "min !" of the expression (10)) results in selecting each branch. This selecting processes are indicated in the expressions (11) to (14) and the Trellis diagram of patterns 1 to 4 (denoted as pattern1 to pattern4).
______________________________________ ##STR1## 8 #STR2## ______________________________________
Of these patterns, the condition of the expression (14) does not permit the existence of the pattern4. The Viterbi algorithm of PR(1,1) can include only three patterns (pattern1 to pattern3) of the state transition.
Further, the expressions (11) to (13) are variable-converted with .DELTA.Lk=-2yp+.beta.. The converted expressions are made to be the following expressions (15) to (17).
From the calculated result of the difference metric, the transformation of the expressions (15) to (17) as remarking the new variables yp and P results in forming the following expressions (18) to (20) and the pattern1 to pattern3 as indicated in the Trellis diagram.
__________________________________________________________________________ .beta. = +1 or .beta. = -1 ##STR3## 0 #STR4## __________________________________________________________________________
Hence, the variables yp and .beta. before the sampling time point k makes the calculation relatively simple. Only the calculated result and the comparison of two identification values ((1, 0) or (0, -1)) make it possible to determine the path. On the determined path, the data is decoded. Then, for the next time point k+1, the variables yp and .beta. are updated.
Now, consider these variables yp and .beta..
The type of the shifting direction can be grasped if the previous state is determined if it is S0 or S1, for determining the path, the identification values to be compared by one calculation are changed from three values of (.+-.1, 0) to just one combination of two values (1, 0) or (0, 1). The type of the previous transition is represented by .beta.. yp denotes the value at the transition. In concrete circuit arrangement, .beta. selects two kinds of identification values (0, 1) or (0, -1).
In turn, the description will be oriented to the data decoding system. For pattern1 and pattern3, the data yk sampled at the time point k defines the state at the time point (k-1). Hence, one path up to the time point (k-1) is defined, so that the decoded data may define the values from the state transition to the time point (k-1). In this case, the state of the data at the time point k is not defined. It means that the data at the time point k cannot be defined. For pattern2, it is understood that the state transition is S0 to S1 or S1 to S0. The previous state of the pattern2 is not defined, so that one path up to the current state is not defined. From the state transition diagram of PR(1, 1), the decoded data at the time point k is "1". However, the data at the time point k-1 is not decoded. The operation is executed to keep the previous state (.beta.) of pattern2 and the sampling value (yp) in order to decode the data when one path is defined later and store in memory the data decoded at the time point k-1 or later, before advancing to the next time. With the passage of the time, the state transitions are defined as pattern1 and pattern3, when the kept value ".beta." is used for defining the data at the time point before the advent of the pattern2 (the time point k-1 as mentioned above). At this time, the overall data decoding is terminated. The memory for keeping this data (termed the bus memory) is, therefore, required to provide a capacity of storing the continuous data of the pattern2 on the system.
The concrete circuit for realizing the foregoing method is considered as shown in FIGS. 6 to 8. FIG. 9 shows waveforms of portions appearing when recording the data (source data) in the recording medium 104 and reproducing the recorded data. FIG. 10 shows how the Viterbi decoder arranged as shown in FIGS. 6 to 8 decodes the data reproduced after the data is recorded as shown in FIG. 9.
At first, the description will be oriented to a concrete operation shown in FIG. 1 with reference to FIG. 9.
When the source data shown in FIG. 9 is entered to the terminal 171, the modulator 101 operates to do the eight-to-ten modulation with respect to the source data and then feed the eight-to-ten modulated data. The eight-to-ten modulated data is sent to the pre-coder 102, in which the modulated series xt are coded to the medium series yt according to the predetermined coding rules. Concretely, the pre-coder 102 uses the so-called NRZI (Non Return to Zero Inverted) system for converting the eight-to-ten modulated data into the recording signal as shown in FIG. 9, in which NRZI system the state is inverted only at the bit information of 1 when the bit information 1, 0 of the input series are recorded in correspondence to the two states (for example, N and S poles of the magnetic tape). The recording signal is sent to the recording head through the recording amplifier 103 and then is recorded on the magnetic tape as an example of a recording medium 104. When reproducing the recording medium 104 with the reproducing head, the resulting data is made to be a waveform reproduced through the head (termed the head reproduced waveform) as shown in FIG. 9. This head reproduced waveform is sent to the equalizer 106 through the reproduction amplifier 105. The equalizer 106 operates to convert the head reproduced waveform into an integrally equalized waveform as shown in FIG. 9 and then into the equalized waveform of PR(1, 1) as shown in FIGS. 9 and 10. After the equalized waveform of PR(1, 1) is sampled in the sampling circuit 108, the sampled waveform is sent to the Viterbi decoder 109 having the arrangements shown in FIGS. 6 to 8.
The difference metric operating unit shown in FIG. 6 is arranged to include a register 201 for storing as data yk the data produced by sampling the equalized waveform of PR(1, 1) shown in FIG. 10, entered through the terminal 200, an adder 202 for adding the data yk from the register 201 to the data yp stored in the register 216, a comparator 205 for comparing the output of the adder 202 with an identifying value of +1 or -1, another comparator 206 for comparing the output of the adder 202 with an identifying value of a ground level (0), an EXOR circuit 207 for performing an exclusive-OR operation of the output data from the comparators 205 and 206, a logical circuit 208 for performing an exclusive-NOR of the output data of the comparator 206 and the data .beta. stored in the register 212, an inverter (NOT circuit) 215 for inverting the output of the register 21, an inverter (NOT circuit) 211 for inverting the output of the comparator 206, an inverter (NOT circuit) 213 for inverting the output of the register 212, a switch 217 for switching the input to the register 216, another switch 214 for switching the input to the register 212, and another switch 204 for setting a reference value (identifying value) of +1 or -1 of the comparator 205.
The terminal 200 shown in FIG. 6 receives the data produced by sampling the equalized waveform of PR(1, 1) shown in FIG. 10. The data is stored as data yk of FIG. 10 in the register 201. The data yk of this register 201 is added to the data yp from the register 216 by the adder 202 (yp+yk). In the initial state, the register 216 stores a given initial value.
The output of the adder 202 is compared with the ground level (0), concretely, is determined to be larger than (yp+yk&lt;0) the ground level (0) in the comparator as shown in FIG. 10. The compared result is output from the comparator 206. The output of the adder 202 is compared with a value of +1 or -1 (yp+yk&lt;.+-.1). The compared result is output to the comparator 205.
The EXOR circuit 207 takes an exclusive-OR of the output of the comparator 205 (the data of 0 or 1 derived from the compared result of yp+yk&lt;.+-.1) and the output of the comparator 206 (the data of 0 or 1 derived from the compared result of yp+yk&lt;0) as shown in FIG. 10. The calculated result is output as the data x from the terminal 209 and sent as the switching control signals to the switches 217 and 214.
The logical circuit 208 takes an exclusive-NOR of the output of the comparator 206 (the data of 0 or 1 derived from the compared result of yp+yk&lt;0) and the data .beta. from the register 212 as shown in FIG. 10. The calculated result is inverted by the inverter 211 and then is sent to the register 212 through the switch 214. In the initial state, the register 212 stores a given initial value.
The switch 214 is served to supply as the data .beta. to be stored in the register 212 any one of the output data of the comparator 206 inverted by the inverter 211 and the output data of the register 212 inverted by the inverter 213 according to the data x from the EXOR circuit 207. The switch 217 is served to supply as the data yk to be stored in the register 216 any one of the output data of the register 201 and the data yp of the register 216 inverted by the inverter 215, according to the data x from the EXOR circuit 207. The switch 204 is served to select the data of +1 or -1 and supply it to the comparator 205 according to the data .beta. of the register 212.
The terminal 200 shown in FIG. 6 receives the data produced by sampling the equalized waveform of PR(1, 1) shown in FIG. 10. The switches 217 and 214 are changed over according to the output data x of the EXOR circuit 207, while the switch 204 is changed over according to the output data .beta. of the register 212, so that the reed data rd1 of FIG. 10 is output from the terminal 210 shown in FIG. 6.
Next, the data x output from the terminal 209 shown in FIG. 6 is supplied to the load terminal of a four-bit counter 220 of the data decoding unit. The four-bit output of this four-bit counter 220 is decoded into 16-bit data by the decoder 221 and then is output.
The reed data rd1 output from the terminal 210 shown in FIG. 6 and the data x output from the terminal 209 are sent to the bus memory unit shown in FIG. 8. In the arrangement of FIG. 8 includes 17 flip-flops 237.sub.0 to 237.sub.16 and switches 236.sub.0 to 236.sub.16 for switching the data rd1 supplied through the terminal 210 of FIG. 6 or the input data k, k-1, . . . , k-16 to each of the flop-flops 237.sub.0 to 237.sub.16 according to the data x sent from the terminal 209 of FIG. 6 or the data pp0 to pp15 supplied from the terminals 241.sub.0 to 241.sub.15 from the decoder 221 of FIG. 7.
The foregoing system advantageously provides a simplified Viterbi decoder but an ACS (Add Compare Select) loop for performing a difference metric operation shown in FIG. 6. This loop is required to be operated within one clock. However, the operating frequency of the circuit is critical. Hence, the foregoing arrangement makes it difficult to achieve a high transfer rate.